#include <stdio.h>
#include <string.h>

// 直接插入排序
void InsertionSort(int R[], int n) {
    int i, j, key;
    for (i = 1; i < n; ++i) {
        key = R[i];  // 记录当前值
        j = i - 1;
        while (j >= 0 && R[j] > key)
        {
            R[j + 1] = R[j];
            j=j-1;
        }
        R[j + 1] = key;
    }
}


// 打印数组函数
void PrintArray(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

// 检查数组是否已排序
int IsSorted(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        if (arr[i] < arr[i-1]) {
            return 0;  // 未排序
        }
    }
    return 1;  // 已排序
}

// 测试函数
void TestInsertionSort() {
    printf("=== 直接插入排序测试 ===\n\n");
    
    // 测试用例1：一般情况
    printf("测试1：一般情况\n");
    int arr1[] = {64, 34, 25, 12, 22, 11, 90};
    int n1 = sizeof(arr1) / sizeof(arr1[0]);
    printf("排序前: ");
    PrintArray(arr1, n1);
    InsertionSort(arr1, n1);
    printf("排序后: ");
    PrintArray(arr1, n1);
    printf("结果: %s\n\n", IsSorted(arr1, n1) ? "✓ 正确" : "✗ 错误");
    
    // 测试用例2：已排序数组
    printf("测试2：已排序数组\n");
    int arr2[] = {1, 2, 3, 4, 5};
    int n2 = sizeof(arr2) / sizeof(arr2[0]);
    printf("排序前: ");
    PrintArray(arr2, n2);
    InsertionSort(arr2, n2);
    printf("排序后: ");
    PrintArray(arr2, n2);
    printf("结果: %s\n\n", IsSorted(arr2, n2) ? "✓ 正确" : "✗ 错误");
    
    // 测试用例3：逆序数组
    printf("测试3：逆序数组\n");
    int arr3[] = {5, 4, 3, 2, 1};
    int n3 = sizeof(arr3) / sizeof(arr3[0]);
    printf("排序前: ");
    PrintArray(arr3, n3);
    InsertionSort(arr3, n3);
    printf("排序后: ");
    PrintArray(arr3, n3);
    printf("结果: %s\n\n", IsSorted(arr3, n3) ? "✓ 正确" : "✗ 错误");
    
    // 测试用例4：单个元素
    printf("测试4：单个元素\n");
    int arr4[] = {42};
    int n4 = sizeof(arr4) / sizeof(arr4[0]);
    printf("排序前: ");
    PrintArray(arr4, n4);
    InsertionSort(arr4, n4);
    printf("排序后: ");
    PrintArray(arr4, n4);
    printf("结果: %s\n\n", IsSorted(arr4, n4) ? "✓ 正确" : "✗ 错误");
    
    // 测试用例5：重复元素
    printf("测试5：重复元素\n");
    int arr5[] = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3};
    int n5 = sizeof(arr5) / sizeof(arr5[0]);
    printf("排序前: ");
    PrintArray(arr5, n5);
    InsertionSort(arr5, n5);
    printf("排序后: ");
    PrintArray(arr5, n5);
    printf("结果: %s\n\n", IsSorted(arr5, n5) ? "✓ 正确" : "✗ 错误");
    
    // 测试用例6：负数
    printf("测试6：包含负数\n");
    int arr6[] = {-3, 5, -1, 0, 8, -2};
    int n6 = sizeof(arr6) / sizeof(arr6[0]);
    printf("排序前: ");
    PrintArray(arr6, n6);
    InsertionSort(arr6, n6);
    printf("排序后: ");
    PrintArray(arr6, n6);
    printf("结果: %s\n\n", IsSorted(arr6, n6) ? "✓ 正确" : "✗ 错误");
    
    printf("=== 所有测试完成 ===\n");
}

// 主函数
int main() {
    TestInsertionSort();
    return 0;
}